import random
from alg import TreeNode

def generate_binary_tree(depth=4, min_val=1, max_val=10):

    if depth <= 0 or random.random() < 0.3: 
        return None
    
    val = random.randint(min_val, max_val)
    root = TreeNode(val)
    root.left = generate_binary_tree(depth - 1, min_val, max_val)
    root.right = generate_binary_tree(depth - 1, min_val, max_val)
    
    return root


def create_example_trees():

    tree1 = TreeNode(3)
    tree1.left = TreeNode(2)
    tree1.right = TreeNode(3)
    tree1.left.right = TreeNode(3)
    tree1.right.right = TreeNode(1)
    
  
    tree2 = TreeNode(3)
    tree2.left = TreeNode(4)
    tree2.right = TreeNode(5)
    tree2.left.left = TreeNode(1)
    tree2.left.right = TreeNode(3)
    tree2.right.right = TreeNode(1)
    

    tree3 = TreeNode(5)
    

    tree4 = None
    

    tree5 = TreeNode(10)
    tree5.left = TreeNode(5)
    tree5.right = TreeNode(15)
    tree5.left.left = TreeNode(3)
    tree5.left.right = TreeNode(8)
    tree5.right.left = TreeNode(12)
    tree5.right.right = TreeNode(20)
    tree5.left.left.left = TreeNode(1)
    tree5.left.right.left = TreeNode(6)
    tree5.right.right.right = TreeNode(25)
    
    return [
        ("示例1: [3,2,3,null,3,null,1]", tree1, 7),
        ("示例2: [3,4,5,1,3,null,1]", tree2, 9),
        ("示例3: 单个节点", tree3, 5),
        ("示例4: 空树", tree4, 0),
        ("示例5: 复杂树", tree5, None)  
    ]


def print_tree(root, prefix="", is_last=True):

    if root is None:
        return
    
    print(prefix + ("└── " if is_last else "├── ") + str(root.val))
    
    children = []
    if root.left is not None:
        children.append((root.left, False))
    if root.right is not None:
        children.append((root.right, True))
    elif root.left is not None:
        children = [(root.left, True)]
    
    for i, (child, is_child_last) in enumerate(children):
        extension = "    " if is_last else "│   "
        if i == len(children) - 1:
            is_child_last = True
        print_tree(child, prefix + extension, is_child_last)


def tree_to_array(root):

    if not root:
        return []
    
    result = []
    queue = [root]
    
    while queue:
        node = queue.pop(0)
        if node:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)
        else:
            result.append(None)
    
    # 移除末尾的None
    while result and result[-1] is None:
        result.pop()
    
    return result


def generate_test_cases():
    test_cases = create_example_trees()

    for i in range(3):
        tree = generate_binary_tree(depth=random.randint(2, 5), min_val=1, max_val=15)
        test_cases.append((f"随机测试用例 {i+1}", tree, None))
    
    return test_cases
